Nous sommes toutes distinctes - Olympiades 2024 Exercice 2

Dans cet exercice, le symbole  $n$ désigne un entier naturel, avec  $n\ge 1$ ; tous les ensembles considérés sont non vides, finis et constitués de nombres réels distincts ; de plus, on conviendra d’écrire tout ensemble fini  $A=\{a_1,\dots ,a_n\}$ à  $n$ éléments réels distincts en ordonnant toujours $a_1,a_2,\cdots ,a_n$  si bien que \(a_1< a_2< \cdots. Étant donné un tel ensemble, on note  $S(A)$ la somme de ses éléments, soit :

$S(A)=a_1+\cdots +a_n$

$$ En particulier, lorsque  $n=1$ et donc  $A=\{a_1\}$  est un singleton,  $S(A)=a_1$ .

On dit que l’ensemble  $A$ est à sommes toutes distinctes (en abrégé que  $A$ est STD) quand, pour toutes parties non vides distinctes  $Y$ et  $Z$ de $A$ , $S(Y)\ne S(Z)$ . Cela revient à demander aux  $2^n-1$ sommes que l’on peut former avec des éléments de  $A$  d’être toutes distinctes.

Par exemple,  $A=\{1,2,5\}$ est STD parce que les nombres $1,2,5,1+2=3,2+5=7,1+5=6,1+2+5=8$   sont tous distincts. En revanche,  $A=\{2,4,6,7\}$ n’est pas STD parce qu’en prenant  $Y=\{2,4,7\}$ et $Z=\{6,7\}$ , on a  $S(Y)=2+4+7=13$   $=S(Z)$ , bien que $Y\ne Z$ .

Partie 1 - Exemples et contre-exemples simples

1. Expliquer pourquoi le nombre de sommes à envisager pour étudier le caractère STD de  $A$ vaut $2^n-1$ .

2. Montrer que l’ensemble  $\{1,3,5\}$ est STD mais que l’ensemble $\{4,6,7,9\}$  ne l’est pas.

3. Quel(s) ensemble(s)  $A$ contenant  $0$ est (sont) STD  ?

4. Soit  $A$ et  $B$ deux ensembles non vides et finis de réels distincts, avec  $A\subset B$ (c’est-à-dire que  $A$ est un sous-ensemble de $B$ ).
    a. Si  $B$ est STD, justifier que  $A$ l’est aussi.
    b. L’ensemble  $B$ peut-il être STD si  $A$ ne l’est pas ? 

5. Soit  $A$ un ensemble non vide et fini de réels distincts. On suppose que  $A$ n’est constitué que de nombres entiers et qu’il est STD. Justifier que  ${\displaystyle A\cup \left\{\frac{1}{2}\right\}}$ puis que  ${\displaystyle A\cup \{\frac{1}{2},\sqrt{2}\}}$ sont aussi STD.

Partie 2 - Construction d’une suite

On considère la suite  $(u_n)$ définie par  $u_1=1$ et par la relation de récurrence, valable pour tout $n\ge 1$ ,

$u_{(n+1)}=u_1+\cdots +u_n+1$

6. Vérifier que $u_2=2$  et $u_3=4$ . Calculer $u_5$ .

7. Rédiger sur votre copie un programme en langage Python qui renverrait  $u_{100}$ (qu’on ne calculera pas).

8. Étudier le sens de variation de la suite $(u_n)$ .

9. Montrer que, pour tout $n\ge 1$ , l’ensemble  $\{u_1,\cdots ,u_n\}$ est STD.

10. Montrer que  $(u_n)$ est en fait une suite géométrique que l’on déterminera.

Partie 3 - Suites STD

Une suite  $(u_n)$ est dite STD lorsqu’elle est strictement croissante, qu’elle est composée d’entiers strictement positifs et que, pour tout $n\ge 1$ , l’ensemble  $\{u_1,\cdots ,u_n\}$ est STD.

Par exemple, la suite étudiée dans la partie 2 est une suite STD.

11. Soit (𝑢𝑛) une suite STD quelconque.
    a. Montrer que pour tout  $n\ge 1$ :  $u_1+\cdots +u_n\ge 2^n-1$ .

     b. En déduire que pour tout  $n\ge 2$ :  $u_n\ge {\displaystyle \frac{2^n}{n}}$ .

12. Le but cette question est d’affiner la minoration obtenue à la question précédente. Pour ce faire, nous aurons recours aux probabilités, et nous dirons qu’une variable aléatoire  $X$ à valeurs dans un ensemble réel fini non vide $A=\{a_1,\cdots ,a_n\}$  à  $n$ éléments distincts suit une loi uniforme quand toutes les valeurs qu’elle peut atteindre sont équiprobables. Ainsi,

$P(X=a_1)=P(X=a_2)=\cdots =P(X=a_n)={\displaystyle \frac{1}{n}}$ .
    a. Soit  $(u_n)$ une suite STD quelconque. Pour  $n\ge 2$ , on considère les variables aléatoires indépendantes  $X_1,\dots ,X_n$ qui suivent la loi uniforme sur la paire  $\{-1,1\}$ : ainsi, pour chacun des indices $i,P(X_i=1)=P(X_i=-1)={\displaystyle \frac{1}{2}}$ . 
On pose $X=u_1{X}_1+\cdots +u_n{X}_n$ .
On admet que $E(X)=u_{1}E(X_1)+\cdots +u_{n}E(X_n)$  et que $V(X)=u_1^{2}V(X_1)+\dots +u_n^2(X_n)$ .
Après avoir justifié que  $E(X_1)=0$ et $V(X_1)=1$ , calculer l’espérance  $E(X)$ et exprimer la variance  $V(X)$ en fonction de $u_1,u_2,\cdots ,u_n$ .
    b. Montrer que  $X$ suit une loi uniforme sur un ensemble de  $2^n$ entiers relatifs, symétrique par rapport à $0$ , et dont les éléments sont non nuls et de la même parité.
    c. En déduire que pour $n\ge 1$ ,  ${u_n}^2\ge {\displaystyle \frac{1}{n{2}^{n-1}}}(1^2+3^2+5^2+\cdots +(2^n-1{)}^2)$ .
    d. Proposer une valeur de  $n\ge 2$ pour laquelle cette inégalité fournit un minorant plus grand qu’en 11.b.